package 牛客.树;
/*
 * @Author   helen
 * @Date     2021/4/16 11:09
 * @Descriptions
 * 题目描述
    输入一棵二叉树，判断该二叉树是否是平衡二叉树。
    在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
    平衡二叉树（Balanced Binary Tree），具有以下性质：
    * 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    示例1
        输入     {1,2,3,4,5,6,7}
        返回值    true
 */

public class 平衡二叉树 {
    public boolean IsBalanced_Solution(BTreeNode<Integer> root) {
        if(root == null)
            return true;
        int left = depth(root.left);
        int right = depth(root.right);
        if(left-right > 1 || left-right < -1)
            return false;
        //判断子树是否是平衡二叉树
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    //判断树的深度
    public int depth(BTreeNode<Integer> root){
        if(root == null)
            return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        return left>right? left+1 : right+1;
    }

    public static void main(String[] args) {
        平衡二叉树 obj = new 平衡二叉树();
        BTree tree = new BTree();
        for (int i = 0; i < 10; i++) {
            tree.RandomCreatTree(tree.root, i);
        }
        System.out.println(obj.IsBalanced_Solution(tree.root));
    }
}
